package leetcode.problems;

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by gmwang on 2018/7/25
 * 翻转string
 */
public class _0810CountingBits {
    /**
     *
     * Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
     *给定一个非负整数num，对于范围0≤i≤num的每个数字，计算它们的二进制表示中的1的个数，并将它们作为数组返回。
     * Example 1:
     *
     * Input: 2
     * Output: [0,1,1]
     * Example 2:
     *
     * Input: 3
     * Output: [0,1,1,2]
     * Example 2:
     *
     * Input: 5
     * Output: [0,1,1,2,1,2]
     * Follow up:
     *
     *  Input: 6
     *  Output: [0,1,1,2,1,2,1]
     *
     *  Input: 7
     *  Output: [0,1,1,2,1,2,1,2]
     *  Follow up:
     *
     * Input: 8
     * Output: [0,1,1,2,1,2,2,3,1]
     *
     * Follow up:
     * It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
     * Space complexity should be O(n).
     * Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
    /**
     *
     * @param num
     * @return
     */
//    public int[] countBits(int num) {
//        int [] res = new int[num+1];
//        for (int i = 0; i < num + 1; i++) {
//            for(int m = 31;m >= 0; m--){
//                if((i >>> m & 1) == 1) res[i]+=1;
//            }
//        }
//        return res;
//    }

    public int[] countBits(int num) {
        int[] f = new int[num + 1];
        for (int i=1; i<=num; i++){
            f[i] = f[i >> 1] + (i & 1);
        }
        return f;
    }

    public int binaryToDecimal(int n){
        int res = 0;
         for(int i = 31;i >= 0; i--){
             if((n >>> i & 1) == 1) res ++;
         }
         return res;
       }
    @Test
    public void test() {
//        int[] ints = {0,1,1,2,1,2};
        int ints = 4;
        int[] res = countBits(ints);
        System.out.println(Arrays.toString(res));
//        System.out.println(binaryToDecimal(6));
//        int log = (int)(Math.log(8) / Math.log(2));
        System.out.println(4>>1);
        //[0,1,1,2,1,2,2,3,1]
    }
}
